package algorithm.dynamic;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/coin-change-2/
 * Medium
 *
 * 给了硬币面额组合 coins 和 需要的总数amount
 * 找出所有可以组成amount总和的，硬币组合数
 *
 *
 * 思路：
 * 假设
 * Created by yzy on 2021-03-08 11:19
 */
public class CoinChange2 {

    public static void main(String[] args) {
        int[] coins = new int[]{1,2,5};
        System.out.println(change(5, coins));
    }


    /**
     * 该问题类似爬楼梯，只不过爬楼梯是一次只能1 2 阶
     * 这个相当于，一次阶梯的情况是coins而已。
     * @param amount
     * @param coins
     * @return
     */
    public static int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, 0);
        dp[0] = 1;
        // 循环的顺序不能错，只有先coin 才是组合数
        for(int coin : coins){
            for(int i=coin; i<=amount; ++i){
                dp[i] = dp[i] + dp[i-coin];
            }
        }
        return dp[amount];
    }
}
